package java111_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Day25 {
    // https://www.nowcoder.com/practice/17865bc2a75c4944a872ef709958c56e?tpId=290&tqId=39933&ru=/exam/oj
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.next();
            int max = 1, min = 100;
            int[] arr = new int[26];
            for(int i = 0; i < str.length(); i++){
                int index = str.charAt(i) - 'a';
                arr[index]++;
            }
            for(int i = 0; i < 26; i++){
                if(arr[i] == 0){
                    continue;
                }
                if(max < arr[i]){
                    max = arr[i];
                }
                if(min > arr[i]){
                    min = arr[i];
                }
            }
            if(isZS(max-min)){
                System.out.println("Lucky Word");
                System.out.println(max-min);
            } else {
                System.out.println("No Answer");
                System.out.println(0);
            }
        }
    }
    public static boolean isZS(int x){
        if(x < 2) {
            return false;
        }
        int end = (int) Math.sqrt(x);
        for(int i = 2; i <= end; i++){
            if(x % i == 0){
                return false;
            }
        }
        return true;
    }

    //https://www.nowcoder.com/practice/e160b104354649b69600803184094adb?tpId=196&tqId=40514&ru=/exam/oj
    public boolean hostschedule (ArrayList<ArrayList<Integer>> schedule) {
        Integer[][] arr = new Integer[schedule.size()][schedule.get(0).size()];
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                arr[i][j] = schedule.get(i).get(j);
            }
        }
        Arrays.sort(arr, (Integer[] x1, Integer[] x2) -> {
            return x1[0] - x2[0];
        });
        for(int i = 0; i < arr.length-1; i++){
            if(arr[i][1] > arr[i+1][0]){
                return false;
            }
        }
        return true;
    }


    //https://www.nowcoder.com/practice/65ade309fa4d4067a9add749721bfdc0?tpId=230&tqId=40433&ru=/exam/oj
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt(), sum = 0;
            int[] arr = new int[n+1];
            for(int i = 1; i <= n; i++){
                arr[i] = in.nextInt();
                sum += arr[i];
            }
            if(sum % 2 != 0){
                System.out.println("false");
                continue;
            } else {
                sum /= 2;
            }
            boolean[][] dp = new boolean[n+1][sum+1];
            // dp[i][j] 表示从前 i 个数中选，总和恰好为 j 能否选出
            dp[0][0] = true;
            for(int i = 1; i <= n; i++){
                for(int j = 0; j <= sum; j++){
                    if(j - arr[i] >= 0){
                        dp[i][j] = dp[i-1][j] || dp[i-1][j - arr[i]];
                    } else {
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
            if(dp[n][sum]){
                System.out.println("true");
            } else {
                System.out.println("false");
            }
        }
    }
}
